﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Union_Find
{
    public class UFV3 : IUF
    {
        private int[] id;
        private int[] size;
        private int count;
        public UFV3(int n)
        {
            count = n;
            id = new int[n];
            for (int i = 0; i < n; i++) id[i] = i;
            size = new int[n];
            for (int i = 0; i < n; i++) size[i] = 1;
        }

        public void Union(int p, int q)
        {
            int i = Find(p);
            int j = Find(q);

            if (i == j) return;

            if(size[i] < size[j])
            {
                id[i] = j;
                size[j] += size[i];
            }
            else
            {
                id[j] = i;
                size[i] += size[j];
            }

            count--;
        }

        public int Find(int p)
        {
            while (p != id[p]) p = id[p];
            return p;
        }

        public bool Connected(int p, int q)
        {
            return Find(p) == Find(q);
        }

        public int Count => count;
    }
}
